import matplotlib.pyplot as plt
from alg import Solution
import numpy as np
import time

class test_N_queens:
    so = Solution()

    lengths = [6, 7, 8, 9, 10, 11, 12]
    times = []

    def normalization(ref, base):
        # 使用最大值进行归一化，这样可以保持曲线的相对形状
        return [x/ref[0] * base[0] for x in ref]

    n = np.array(lengths)
    n2 = n ** 2
    facto = np.array([np.math.factorial(x) for x in n])

    for length in lengths:
        start_time = time.perf_counter()
        so.solveNQueens(length)
        end_time = time.perf_counter()
        times.append(end_time - start_time)
        print(f"长度为{length}的测试用例，运行时间为{end_time - start_time}秒")

    plt.plot(n, times, 'bo-',label = "Measured Time", linewidth = 2)
    plt.plot(n, normalization(n2, times), 'r--',label = "O(n^2)", linewidth = 2)
    plt.plot(n, normalization(facto, times), 'g--',label = "O(n!)", linewidth = 2)
    plt.plot(n, normalization(n, times), 'm--', label = "O(n)", linewidth = 2)

    # 设置y轴为对数刻度，这样可以更好地显示不同数量级的数据
    plt.yscale('log')
    plt.xlabel('Length of input list')
    plt.ylabel('Time (seconds)')
    plt.title('N Queens Performance Analysis')
    plt.grid(True)
    plt.legend()
    plt.tight_layout()
    plt.show()
    plt.savefig('N_Queens.png')

if __name__ == "__main__":
    test = test_N_queens()
